package problems.daily.y2021m7;

import java.util.Arrays;

/**
 * @author habitplus
 * @since 2021-07-02 09:18
 */
public class T20210702N1 {
    // 夏日炎炎，小男孩 Tony 想买一些雪糕消消暑。
    // 商店中新到 n 支雪糕，用长度为 n 的数组 costs 表示雪糕的定价，其中 costs[i] 表示第 i 支雪糕的现金价格。
    // Tony 一共有 coins 现金可以用于消费，他想要买尽可能多的雪糕。
    // 给你价格数组 costs 和现金量 coins ，请你计算并返回 Tony 用 coins 现金能够买到的雪糕的 最大数量 。
    // 注意：Tony 可以按任意顺序购买雪糕。
    // 提示：
    //      costs.length == n
    //      1 <= n <= 10^5
    //      1 <= costs[i] <= 10^5
    //      1 <= coins <= 10^8

    public int maxIceCreamByGreedy(int[] costs, int coins) {
        // 排序 + 贪心
        // List<Integer> list = Arrays.stream(costs).boxed().collect(Collectors.toList());
        // Collections.sort(list);
        Arrays.sort(costs);

        int i = 0;
        while (i < costs.length && costs[i] <= coins) {
            coins -= costs[i];
            i++;
        }

        return i;
    }

    public int maxIceCreamByBucketSort(int[] costs, int coins) {
        // 桶排序：记录每种价格的冰激凌的种类数
        int len = 100001;
        int[] fre = new int[len];

        for (int cost : costs) {
            fre[cost]++;
        }

        int minCnt;
        int cnt = 0;
        for (int i = 1; i < len; i++) {
            if (coins < i) {
                break;
            }

            // 优化：如果当前价格没有冰激凌售出，则直接枚举下一个价格
            if (fre[i] == 0) {
                continue;
            }

            // 同样价格的冰激凌的数量 and 最多能买到的数量，取较小值
            minCnt = Math.min(coins / i, fre[i]);
            coins -= (minCnt * i);
            cnt += minCnt;
        }

        return cnt;
    }

}
